from typing import List

class Solution1:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        path = [0] * n

        def dfs(i, s):
            if i == n:
                ans.append(path.copy())
            for x in s:
                path[i] = x
                dfs(i + 1, s - {x})

        dfs(0, set(nums))
        return ans


class Solution2:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        path = [0] * n
        on_path = [False] * n

        def dfs(i):
            if i == n:
                ans.append(path.copy())
                return
            for j in range(n):
                if not on_path[j]:
                    path[i] = nums[j]
                    on_path[j] = True
                    dfs(i + 1)
                    on_path[j] = False

        dfs(0)
        return ans

# 以下是测试代码
solution = Solution2()
nums = [1, 2, 3]
print(solution.permute(nums))

#洛谷P1706
def permute(n):
    nums = list(range(1, n + 1))
    ans = []
    path = [0] * n
    on_path = [False] * n

    def dfs(i):
        if i == n:
            ans.append(path.copy())
            return
        for j in range(n):
            if not on_path[j]:
                path[i] = nums[j]
                on_path[j] = True
                dfs(i + 1)
                on_path[j] = False

    dfs(0)
    for perm in ans:
        for num in perm:
            print(f"{num:5d}", end="")
        print()


# 读取输入
n = int(input())
permute(n)


